package com.celan.year2023.month02.day13;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int balancedString(String s) {
        int n = s.length();
        //如果除开字串,其他字符串都满足 <= n/4,则说明修改该字串满足题目条件
        int target = n / 4;
        int[] cnt = new int[26];
        //统计原字符串各个字母个数
        for (int i = 0; i < n; i++) cnt[s.charAt(i) - 'A']++;
        if (check(cnt, target)) return 0;

        int res = n;
        //枚举字串右端点
        for (int right = 0, left = 0; right < n; right++) {
            cnt[s.charAt(right) - 'A']--;
            //如果满足条件,将左指针持续缩小
            while (left <= right && check(cnt, target)) {
                res = Math.min(res, right - left + 1);
                ++cnt[s.charAt(left++) - 'A']; //缩小子串
            }
            //不满足条件将右指针右移
        }
        return res;
    }

    private boolean check(int[] cnt, int target) {
        if (cnt['Q' - 'A'] <= target && cnt['W' - 'A'] <= target
                && cnt['E' - 'A'] <= target && cnt['R' - 'A'] <= target) {
            return true;
        }
        return false;
    }

    int[] temp;
    int[] res;
    int[] idxs;
    int[] nums;
    List<Integer> result = new ArrayList<>();

    public List<Integer> countSmaller(int[] nums) {
        this.nums = nums;
        int len = nums.length;
        if (len == 0) return result;
        temp = new int[len];
        res = new int[len];
        // 索引数组，作用：归并回去的时候，方便知道是哪个下标的元素
        idxs = new int[len];
        for (int i = 0; i < len; i++) idxs[i] = i;

        mergeAndCountSmaller(0, len - 1);

        // 把int[]转换成为List<Integer>,没有业务逻辑
        for (int i = 0; i < len; i++) result.add(res[i]);
        return result;
    }

    //针对数组nums指定的区间[left, right]进行归并排序,在排序的过程中完成统计任务
    private void mergeAndCountSmaller(int left, int right) {
        //终止条件
        if (left == right) return;
        int mid = left + (right - left) / 2;
        //分而治之
        mergeAndCountSmaller(left, mid);
        mergeAndCountSmaller(mid + 1, right);
        //归并排序的优化，如果索引数组有序，则不存在逆序关系，没有必要合并
        if (nums[idxs[mid]] <= nums[idxs[mid + 1]]) return;
        //进行归并
        mergeOfTwoSortedArrAndCountSmaller(left, mid, right);
    }

    //归并逻辑
    //[left, mid] 是排好序的，[mid + 1, right] 是排好序的
    private void mergeOfTwoSortedArrAndCountSmaller(int left, int mid, int right) {
        //记录原始下标
        for (int i = left; i <= right; i++) {
            temp[i] = idxs[i];
        }

        //指针i指向数组最左端
        int i = left;
        //指针j指向mid+1
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                idxs[k] = temp[j];
                j++;
            } else if (j > right) {
                idxs[k] = temp[i];
                i++;
                res[idxs[k]] += (right - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                // 注意：这里是 <= ，保证稳定性
                idxs[k] = temp[i];
                i++;
                res[idxs[k]] += (j - mid - 1);
            } else {
                idxs[k] = temp[j];
                j++;
            }
        }
    }
}